package top.dprkshow.practice.hashtable;

/**
 * @author Kent HAN
 * @date 2021/8/15
 */
public class MyHashTable {
    KeyValue[] data;

    int kTableSize = 100;

    MyHashTable () {
        this.data = new KeyValue[kTableSize];
    }

    int hash(String str, int m) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash = hash * 31 + str.charAt(i);
        }
        return Math.abs(hash) % m;
    }

    void printDebug() {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == null) {
                System.out.println(i + ": ");
            } else {
                System.out.println(data[i].key + ": " + data[i].value);
            }
        }
    }

    // Returns true if the given key exists in the table
    boolean exists(String key){
        return get(key) != null;
    }

    // Add the given key and object to hash table. If key exists, update the value.
    void add(KeyValue object) {
        int index = hash(object.key, kTableSize);
        KeyValue kv = get(object.key);
        if (kv != null) {
            kv.value = object.value;
        } else {
            object.next = data[index];
            data[index] = object;
        }
    }

    // Returns the value associated with the given key, or NULL if it doesn't exist
    KeyValue get(String key) {
        int index = hash(key, kTableSize);
        KeyValue kv = data[index];
        while (kv != null) {
            if (key.equals(kv.key)) {
                return kv;
            }
            kv = kv.next;
        }
        return null;
    }

    // Removes the value associated with key from the table.
    void delete(String key){
        int index = hash(key, kTableSize);
        KeyValue pre = null;
        KeyValue kv = data[index];

        while (kv != null) {
            if (key.equals(data[index].key)) {
                if (pre == null) {
                    data[index] = kv.next;
                } else {
                    pre.next = kv.next;
                }
            }
            pre = kv;
            kv = kv.next;
        }
    }

}
